import random
DIMENSOES = 8 # Proporções fixas do tabuleiro 8x8.
cx = [1, 1, 2, 2, -1, -1, -2, -2]
cy = [2, -2, 1, -1, 2, -2, 1, -1]

class Posicao:
	def __init__(self, x, y):
		self.x = x
		self.y = y

def verificaMov(tabuleiro, x, y):
	return (((x >= 0 and y >= 0) and (x < DIMENSOES and y < DIMENSOES))) and (tabuleiro[y * DIMENSOES + x] < 0)

def retornaGrau(tabuleiro, x, y):
	contador = 0
	for i in range(DIMENSOES):
		if verificaMov(tabuleiro, (x + cx[i]), (y + cy[i])):
			contador += 1
	return contador

# Usa a heurística de Warnsdorff para determinar o próximo movimento.
def proximoMovimento(tabuleiro, posicao):
	menor_grau_id = -1
	c = 0
	menor_grau = (DIMENSOES + 1)
	newx = 0
	newy = 0

	# Busca pela adjacência de menor grau.
	start = random.randint(0, 1000) % DIMENSOES
	for contador in range(0, DIMENSOES):
		i = (start + contador) % DIMENSOES
		newx = posicao.x + cx[i]
		newy = posicao.y + cy[i]
		c = retornaGrau(tabuleiro, newx, newy)
		if ((verificaMov(tabuleiro, newx, newy)) and c < menor_grau):
			menor_grau_id = i
			menor_grau = c

	# Permanecer em -1 significaria que nada foi encontrado acima.
	if (menor_grau_id == -1):
		return None

	# Atualiza valores de newx e newy com as coordenadas a se seguir.
	newx = posicao.x + cx[menor_grau_id]
	newy = posicao.y + cy[menor_grau_id]

	# Define próximo movimento.
	tabuleiro[newy * DIMENSOES + newx] = tabuleiro[(posicao.y) * DIMENSOES + (posicao.x)] + 1

	# Atualiza célula atual.
	posicao.x = newx
	posicao.y = newy

	return posicao

def imprimeFinal(tabuleiro):
	for i in range(DIMENSOES):
		for j in range(DIMENSOES):
			print("%d\t" % tabuleiro[j * DIMENSOES + i], end="")
		print()

def adjacente(x, y, xx, yy):
	for i in range(DIMENSOES):
		if ((x + cx[i]) == xx) and ((y + cy[i]) == yy):
			return True
	return False

def exerceMovimentos(sx, sy):
	# Inicializa tabuleiro.
	tabuleiro = [-1] * DIMENSOES * DIMENSOES

	# Posiciona devidamente nas posições de partida.
	posicao = Posicao(sx, sy)
	tabuleiro[posicao.y * DIMENSOES + posicao.x] = 1 # Marca primeiro movimento.

	# Usa a heurística de Warnsdorff para obter os próximos passos.
	retorno = None
	for i in range(DIMENSOES * DIMENSOES - 1):
		retorno = proximoMovimento(tabuleiro, posicao)
		if retorno == None:
			return False

	if not adjacente(retorno.x, retorno.y, sx, sy):
		return False
	imprimeFinal(tabuleiro)
	return True

if __name__ == '__main__':
	sx = int(input('Informe a linha de partida do cavalo: '))-1
	sy = int(input('Informe a coluna de partida do cavalo: '))-1
	while not exerceMovimentos(sx,sy): # Executa até a conclusão de tudo.
		pass
